#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <math.h>

#define TYPE double

// the use must define this function to use genericScan
void userBinaryOperator( void *x1, void *x2) {
	TYPE *a = (TYPE *) x1;
	TYPE *b = (TYPE *) x2;
	
	*a += *b;
}


void genericScan(double *X, int n) {
	int i, logn, pow_d, pow_d1, d, tmp;
	double *c = X;

	logn = (int)floor(log2(n));

	for (d = 0; d < logn; d++) {
		pow_d = 1 << d;
		pow_d1 = pow_d << 1;

#pragma omp parallel for shared (c) schedule (guided)
		for (i = -1; i < n - pow_d1; i += pow_d1) {
			tmp = i + pow_d1;
			c[tmp] = c[i + pow_d] + c[tmp];
		}
	}

	for (; d >= 0; d--) {
		pow_d = 1 << d;
		pow_d1 = pow_d << 1;

#pragma omp parallel for shared (c) schedule (guided) 
		for (i = -1; i < n - pow_d - pow_d1; i += pow_d1) {
			tmp = i + pow_d + pow_d1;
			c[tmp] = c[i + pow_d1] + c[tmp];
		}
	}
}


// DRIVER
int main( int argc, char **argv) {	
	
	// problem setup
	int n = 20;
	int dim = 1;
	int i;

	if(argc > 1) 
		n = atoi(argv[1]);

	if(argc > 2) 
		dim = atoi(argv[2]);

	TYPE *x = (TYPE *) malloc( sizeof(TYPE) * n);
	
	for(i = 0; i < n; i++)
		x[i] = i % 2;

/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing
	double t1 = omp_get_wtime(); 
	genericScan(x, n);
	double t2 = omp_get_wtime();

/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	printf("\n\tTook %g secs for %d keys\n", t2-t1, n);

	// clean up
	free(x);
	return 0;
}
	




	


	



